package priv.pront.code.national.acwing.graph;

import java.util.Arrays;
import java.util.Scanner;

public class A850_Dijkstra求最短路朴素版 {
    static boolean[] vi;
    static int[][] g;
    static long[] dis;
    static int n ,m;

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt(); m = scanner.nextInt();
        g = new int[n + 1][m + 1];
        vi = new boolean[n + 1];
        dis = new long[n  + 1];
        for(int i = 0; i < g.length;i++) Arrays.fill(g[i], Integer.MAX_VALUE);
        while(m > 0){
            int a = scanner.nextInt(); int b = scanner.nextInt(); int c = scanner.nextInt();
            g[a][b] = Math.min(g[a][b], c);
            m--;
        }
        System.out.println(dijkstra());
    }

    private static long dijkstra(){
        Arrays.fill(dis, Integer.MAX_VALUE);
        dis[1] = 0;
        for(int i = 0; i < n; i++){
            int t = -1;
            for(int j = 1; j <= n; j++){
                if(!vi[j] && (t == -1 || dis[t] > dis[j])) t = j;
            }
            vi[t] = true;
            for(int j = 1; j <= n; j++){
                dis[j] = Math.min(dis[j], dis[t] + g[t][j]);
            }
        }
        return dis[n] == Integer.MAX_VALUE ? -1 : dis[n];
    }
}
